package com.bishi;

/**
 * 给定两个子序列S,T，返回S子序列等于T的不同子序列的个数
 */
public class 微盟2 {
    public static void main(String[] args) {
        String s = "nowcccoder";
        String t = "nowccoder";
        System.out.println(numDistinct(s,t));
    }

    public static int numDistinct (String S, String T) {
        // write code here
        if(S.isEmpty() || T.isEmpty()){
            return 0;
        }
        int lenS = S.length();
        int lenT = T.length();
        int[][] arr = new int[lenS+1][lenT+1];
        arr[0][0] = 1;
        for(int i = 1; i <= lenS; i++){
            arr[i][0] = 1;
        }
        for(int i = 1; i <= lenS; i++){
            for(int j = 1;  j <= lenT; j++){
                if(S.charAt(i-1) == T.charAt(j-1)){
                    arr[i][j] = arr[i-1][j] + arr[i-1][j-1];
                } else {
                    arr[i][j] = arr[i-1][j];
                }
            }
        }
        return arr[lenS][lenT];
    }
}
